package cn.moefly.algorithm.sort;

import java.util.function.BiFunction;

/**
 * 未完成
 */
public class MergeSort implements SortAlgoRithm {

    BiFunction<Integer,Integer,Boolean> compare;

    @Override
    public int[] sort(int[] source, int type) {
        compare = type == ASC ? GT : LT;
        var arr = source.clone();
        innerSort(arr,0,arr.length-1);
        return arr;
    }

    private void innerSort(int[] arr, int start, int end){
        int step = end - start;

        if (step == 1){
            if (compare.apply(arr[start],arr[end])){
                switchNum(arr,start,end);
            }
            return;
        } if (end - start < 1){
            return;
        }

        int devPos = (start + end) / 2;
        innerSort(arr,start,devPos);
        innerSort(arr,devPos+1,end);
        merge(arr, start, end);



    }

    private void merge(int[] arr, int start, int end){

        int devPos = (start + end / 2);

        int[] tmp = new int[end-start+1];

        int a1Ptr = start;
        int a2Ptr = devPos+1;


        int index = 0;
        while (a1Ptr <= devPos && a2Ptr <= end){
            if(compare.apply(arr[a1Ptr],arr[a2Ptr])){
                tmp[index++] = arr[a2Ptr++];
            } else {
                tmp[index++] = arr[a1Ptr++];
            }
        }

        if (a1Ptr >= devPos){
            System.arraycopy(arr,a2Ptr,tmp,index,end-a2Ptr+1);
        } else {
            System.arraycopy(arr,a1Ptr,tmp,index,devPos-a1Ptr+1);
        }

        System.arraycopy(tmp,0,arr,start,tmp.length);
    }


}
